package com.zpself.module.算法练习.计算;

import java.util.HashMap;

/**
 * @author By ZengPeng
 * @Description 给定一个包含 非负数 的数组和一个目标 整数 k，
 * 编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，
 * 即总和为 n*k，其中 n 也是一个整数。
 *
示例 1：
输入：[23,2,4,6,7], k = 6
输出：True
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。
 * @date in  2021/2/6 19:31
 * @Modified By
 */
public class 力扣_523_连续的子数组和 {
    public static void main(String[] args) {

        System.out.println(checkSubarraySum(new int[]{23,2,4,6,7},6));
        System.out.println(checkSubarraySum(new int[]{23,2,6,4,7},13));

    }

    //设位置 j < i :
    //0 到 j 的前缀和 preSum1 = 某常数1 * k + 余数1
    //0 到 i 的前缀和 preSum2 = 某常数2 * k + 余数2
    //当找到 余数1 等于 余数2时， 则 j + 1 到 i 的连续和 = preSum2 - preSum1 = (某常数2 - 某常数1) * k， 必为 k 的倍数， 返回true
    public static  boolean checkSubarraySum(int[] nums, int k) {

        HashMap<Integer,Integer> remainder = new HashMap<>();
        remainder.put(0,-1);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (k != 0)
                sum = sum % k;
            if(remainder.containsKey(sum)){
                if(i-remainder.get(sum)>1) return true;//必须两个数相加
            }else
                remainder.put(sum,i);
        }
        return false;
    }
}
